#pragma once

namespace WTB{

	class CRBTreeNode
	{
	public:
		/*
		*
		*/
		void InitNode();
		/*
		* get next node
		*
		*@return CRBTreeNode* : NULL or node
		*/
		CRBTreeNode* GetNextNode();
		/*
		* get pre node
		*
		*@return CRBTreeNode* : NULL or node
		*/
		CRBTreeNode* GetPreNode();
	private:
		static const unsigned long RED = 0;
		static const unsigned long BLACK = 1;
		friend class CRBTree;
	private:

		CRBTreeNode* GetParent() const
		{
			return m_pParent;
		}
		unsigned long GetColor() const
		{
			return m_ulColor;
		}
		bool IsRed() const
		{
			return RED == GetColor();
		}
		bool IsBlack() const
		{
			return BLACK == GetColor();
		}
		void SetRed() 
		{
			m_ulColor = RED;
		}
		void SetBlack()
		{
			m_ulColor = BLACK;
		}
		void SetParent(CRBTreeNode* _pParent)
		{
			m_pParent = _pParent;
		}
		void SetColor(unsigned long _ulColor)
		{
			m_ulColor = _ulColor;
		}
		void Clear()
		{
			SetParent(this);
		}
		bool IsEmpty() const
		{
			return GetParent() == this;
		}

	private:
		unsigned long m_ulColor;
		CRBTreeNode* m_pParent;
	public:
		CRBTreeNode* m_pLeftChild;
		CRBTreeNode* m_pRightChild;
		void* m_pExpandInfo;
	};

	inline void CRBTreeNode::InitNode()
	{
		m_ulColor = 0;
		m_pLeftChild = NULL;
		m_pRightChild = NULL;
		m_pExpandInfo = NULL;
		Clear();
	}

	class CRBTree
	{
	public:
		CRBTree():
		  m_pRBTreeRoot(NULL)
		  {

		  }
		  static void LinkNode(CRBTreeNode* _pInsertNode,CRBTreeNode* _pParent,CRBTreeNode** _pLinkPoint);

		  void Erase(CRBTreeNode* _pEraseNode);
		  void InsertColor(CRBTreeNode* _pInsertNode);

		  /*
		  * get the first node(most left node)
		  *
		  *@return CRBTreeNode* : NULL or node
		  */
		  CRBTreeNode* GetFirstNode();
		  /*
		  * get the first node(most right node)
		  *
		  *@return CRBTreeNode* : NULL or node
		  */
		  CRBTreeNode* GetLastNode();

	protected:
		void _RotateLeft(CRBTreeNode* _pRotateNode);
		void _RotateRight(CRBTreeNode* _pRotateNode);
		void _EraseColor(CRBTreeNode* _pEraseNode,CRBTreeNode* _pParent);
	public:
		CRBTreeNode* m_pRBTreeRoot;
	};

	inline void CRBTree::LinkNode(
		CRBTreeNode* _pInsertNode,
		CRBTreeNode* _pParent,CRBTreeNode** _pLinkPoint)
	{
		_pInsertNode->SetParent(_pParent);
		_pInsertNode->SetColor(CRBTreeNode::RED);
		_pInsertNode->m_pLeftChild = _pInsertNode->m_pRightChild = NULL;

		*_pLinkPoint = _pInsertNode;
	}

}